package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 871. 最低加油次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/2 10:55
 */
public class MinRefuelStops {

    public static void main(String[] args) {
        MinRefuelStops test = new MinRefuelStops();

        // 2
        int t = 100;
        int s = 10;
        int[][] arr = {{10, 60}, {20, 30}, {30, 30}, {60, 40}};

        // 4
//        int t = 1000;
//        int s = 83;
//        int[][] arr = {{47,220},{65,1},{98,113},{126,196},{186,218},{320,205},{686,317},{707,325},{754,104},{781,105}};

        int i = test.minRefuelStops(t, s, arr);
        System.out.println(i);
    }


    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if (startFuel >= target) {
            return 0;
        }
        int length = stations.length;
        if (length == 0) {
            return -1;
        }
        int[][] arr = new int[length + 1][length + 1];
        arr[0][1] = startFuel;
        for (int i = 1; i <= length; i++) {
            if (stations[i - 1][0] <= startFuel) {
                arr[i][1] = Math.max(startFuel + stations[i - 1][1], arr[i - 1][1]);
            } else {
                if (stations[i - 1][0] <= arr[i - 1][1]) {
                    arr[i][1] = arr[i - 1][1];
                } else {
                    arr[i][1] = -1;
                }
            }
            if (arr[i][1] >= target) {
                return 1;
            }
        }
        int step = Integer.MAX_VALUE;
        for (int i = 2; i <= length; i++) {
            int[] last = arr[i - 1];
            int[] item = arr[i];
            for (int j = 2; j <= i; j++) {
                int l = last[j - 1];
                if (l == -1) {
                    item[j] = -1;
                } else {
                    if (l < stations[i - 1][0]) {
                        item[j] = -1;
                    } else {
                        item[j] = l + stations[i - 1][1];
                    }
                }
                l = last[j];
                if (l == -1) {
                    break;
                }
                item[j] = Math.max(item[j], l);
                if (item[j] >= target) {
                    step = Math.min(step, j);
                    break;
                }
            }
        }
        return step == Integer.MAX_VALUE ? -1 : step;
    }

}
